1. Field of the Invention
The present invention relates to novel run length encoders and more particularly to a run length encoder for use with a string data compression system to precompresses the input data to the string data compression system.
2. Description of the Prior Art
The present invention novel run length encoder is adapted to perform pre-compression of an input data stream being applied to a high speed data compression system of the type described in Welch U.S. Pat. No. 4,558,302 classified in U.S. Class 341, Subclass 51. Further, the present invention is specifically adapted to precompress the input stream of data applied to a universal controller data compression system of the type employed to control tape systems and/or disk systems set forth in co-pending U.S. Application Ser. No. 202,733 filed June 3, 1988 entitled DATA COMPRESSION/DECOMPRESSION APPARATUS WITH THROTTLE, START-UP AND BACKWARD READ CONTROLS classified in U.S. Class 341, Subclass 60.
The aforementioned Welch Data Compression Algorithm and Method was published in the IEEE "COMPUTER" Vol. 17, No. 6, June 1984, at pages 1-19. Shortly after this publication was distributed, engineers and scientists adapted the technique which was placed on several electronic bulletin boards throughout the United States and has since become virtually a standard in the scientific community and is being presently processed by the International Standards Organization (ISO) as a worldwide standard for modems and similar data compression apparatus. The present invention, by being compatible, offers an enhancement to this standard.
The aforementioned Welch data compression system is capable of accepting characters of length (width) from 8 to 11 bits and to maintain an efficient data compression ratio which is not generally true of other data compression systems.
When prior art 9 bit character data streams are fed into 8 bit selective [sometimes mistakenly called adaptive] Huffman data compression systems, the data compression ratio is severally degraded. The degradation may be so severe that the system is not operable over a general range of different types of data. The Huffman data compression system may be characterized as a character distribution system, thus, if the distribution is disrupted by inputting 9 bit characters into an 8 bit data compression system, the selective Huffman data compression system is virtually neutralized and/or destroyed as an efficient system. Selective Huffman data compression systems take account of the frequency of characters in the input data stream and subsequently select one of a plurality of sets of alphabets stored in a memory library to employ for encoding characters. The most frequent occurring characters are encoded in fewer bits that the input character bits and less frequent occurring characters are expansion-encoded into a greater number of bits than the input character bits.
The aforementioned Welch article in "Computer" states that "Run-length encoding--has virtually no value in text, and has moderate value in data files." While this is true as a general case for run length encoders it is NOT true for the present invention specific run length encoder as will be explained in detail hereinafter. Since Welch data compression is rapidly becoming a worldwide standard to be used in modems, fax machines, etc., it would be extremely desirable to provide a universal data compression system that is automatically adaptable to the width of the bit characters in the bit data stream and provides data compression ratio enhancement to the data to be compressed in Welch data compression systems.